翻訳と辞書 Words near each other ・ Geopora cooperi ・ Geopora sepulta ・ Geometry ・ Geometry & Topology ・ Geometry (disambiguation) ・ Geometry (Ivo Perelman album) ・ Geometry (Jega album) ・ Geometry (Robert Rich album) ・ Geometry and topology ・ Geometry Dash ・ Geometry Expert ・ Geometry Festival ・ Geometry from the Land of the Incas ・ Geometry index ・ Geometry instancing ・ Geometry of binary search trees ・ Geometry of Fear ・ Geometry of interaction ・ Geometry of Love ・ Geometry of numbers ・ Geometry of roots of real polynomials ・ Geometry pipelines ・ Geometry prize ・ Geometry processing ・ Geometry Wars ・ Geomicrobiology ・ Geomipmapping ・ Geomitra ・ Geomitra delphinuloides ・ Geomitra grabhami Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Geometry of binary search trees ： ウィキペディア英語版 Geometry of binary search trees In computer science, one approach to the dynamic optimality conjecture on online algorithms for binary search trees involves reformulating the problem geometrically, in terms of augmenting a set of points in the plane with as few additional points as possible in order to avoid rectangles with only two points on their boundary. ==Access sequences and competitive ratio== As typically formulated, the online binary search tree problem involves search trees defined over a fixed key set (1, 2, ..., ''n''). An ''access sequence'' is a sequence ''x''1, ''x''2, ... where each number ''x''''i'' is one of the given keys. Any particular algorithm for maintaining binary search trees (such as the splay tree algorithm or Iacono's working set structure) has a ''cost'' for each access sequence that models the amount of time it would take to use the structure to search for each of the keys in the access sequence in turn. The cost of a search is modeled by assuming that the search tree algorithm has a single pointer into a binary search tree, which at the start of each search points to the root of the tree. The algorithm may then perform any sequence of the following operations: * Move the pointer to its left child. * Move the pointer to its right child. * Move the pointer to its parent. * Perform a single tree rotation on the pointer and its parent. The search is required, at some point within this sequence of operations to move the pointer to a node containing the key, and the cost of the search is the number of operations that are performed in the sequence. The total cost cost''A''(''X'') for algorithm ''A'' on access sequence ''X'' is the sum of the costs of the searches for each successive key in the sequence. As is standard in competitive analysis, the competitive ratio of an algorithm ''A'' is defined to be the maximum, over all access sequences, of the ratio of the cost for ''A'' to the best cost that any algorithm could achieve: :$\backslash rho\_A\; =\; \backslash sup\_X\; \backslash frac\}(X)\}.$ The dynamic optimality conjecture states that splay trees have constant competitive ratio, but this remains unproven. The geometric view of binary search trees provides a different way of understanding the problem that has led to the development of alternative algorithms that could also (conjecturally) have a constant competitive ratio. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Geometry of binary search trees」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.